class Solution {
    public int singleNumber(int[] nums) {
//        给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//        你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
//        示例 1：
//        输入：nums = [2,2,3,2]
//        输出：3
//        示例 2：
//        输入：nums = [0,1,0,1,0,1,99]
//        输出：99

        //使用哈希表的方式进行解决
        // Map<Integer, Integer> map = new HashMap<>();
        // for(int x : nums){
        //     map.put(x, map.getOrDefault(x, 0) + 1);
        // }
        // for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        //     if(entry.getValue() == 1){
        //         return entry.getKey();
        //     }
        // }
        // return -1;

        //使用位运算的方式解决
        int ret = 0;
        for(int i = 0; i < 32; i++){
            int sum = 0;
            for(int j = 0; j < nums.length; j++){
                if(((nums[j] >> i) & 1) == 1){
                    sum++;
                }
            }
            if((sum %= 3) == 1){
                ret |= (1 << i);
            }
        }
        return ret;
    }
}
